﻿using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Serialization;
using System.Threading;
using System.Threading.Tasks;

namespace SolverTemplateLib.BackTracker
{
    /// <summary>
    /// The 'Backtracker' abstract class
    /// Classes that derive from the abstract Backtracker class must implement a number of methods,
    /// and then get the method Solve to solve the problem with backtracking
    /// </summary>
    [Serializable] 
    public abstract class Backtracker : ISerializable
    {
        /// <summary>
        /// Determines if the Backtracker instance is a solution
        /// </summary>
        /// <returns>
        /// true if object is a solution
        /// </returns>
        public abstract bool IsSolution();

        /// <summary>
        /// Method to process the solution
        /// </summary>
        public abstract void ProcessSolution();

        /// <summary>
        /// Determine new candidate solutions from this candidate.
        /// </summary>
        /// <returns>
        /// </returns>
        public abstract List<Backtracker> Candidates();

        /// <summary>
        /// Method to process the candidate after it is created.
        /// </summary>
        public abstract void ProcessCandidate();

        /// <summary>
        /// Support cancellation
        /// </summary>
        /// <returns>
        /// true if the backtracking is requested to be cancelled.
        /// </returns>
        public abstract bool IsCancelled();

        /// <summary>
        /// The "Template" solve method. It will enumerate all solutions found with backtracking, until finished or cancelled.
        /// To find a single solution, use Linq expression Solve().FirstOrDefault()
        /// </summary>
        /// <returns>
        /// Enumerable list of solutions.
        /// </returns>
        public IEnumerable<Backtracker> Solve()
        {
            if (this.IsSolution())
            {
                this.ProcessSolution();
                yield return this;
            }

            List<Backtracker> C = Candidates();

            // How to: Write a Simple Parallel.ForEach Loop
            // http://msdn.microsoft.com/en-us/library/dd460720.aspx
            // Parallel.ForEach(C, c => { } );
            // But this is not the best solution, because the number of parallel tasks gets too large.
            // E.g the ThreadPool would be better with a condition to add to the pool or do some actual work.

            // int workerThreads;

            int workerThreads = 5;
            int completionPortThreads;

            ThreadPool.GetAvailableThreads(out workerThreads, out completionPortThreads);

            if ((workerThreads > C.Count) && false)
            {
                ConcurrentBag<Backtracker> bag = new ConcurrentBag<Backtracker>();

                if (!IsCancelled())
                {
                    Parallel.ForEach(C, c =>
                        {
                            c.ProcessCandidate();

                            foreach (Backtracker s in c.Solve())
                            {
                                bag.Add(s);
                            }
                        });

                    foreach (Backtracker s in bag)
                    {
                        yield return s;
                    }
                }
            }
            else
            {
                foreach (Backtracker c in C)
                {
                    if (this.IsCancelled())
                        yield break;
                    else
                    {
                        c.ProcessCandidate();

                        foreach (Backtracker s in c.Solve())
                        {
                            yield return s;
                        }
                    }
                }
            }
        }

        /// <summary>
        /// Find only the first solution to the backtracking problem.
        /// </summary>
        /// <returns>
        /// First solution, or default object (null) when no solution was found
        /// </returns>
        public Backtracker FindFirst()
        {
            return Solve().FirstOrDefault();
        }

        /// <summary>
        /// Satisfy Serialization interface
        /// </summary>
        /// <param name="info"></param>
        /// <param name="context"></param>
        public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
        {
        }
    }
}
